這篇文章會用 TDD 手刻 Sequence 版的 myFilter 和 myMap，搞懂 Lazy 操作底層的「包裝 Sequence」設計模式，順便理解為什麼 Sequence 版不適合用 inline

Kotlin ↔ C# 對照表

C# 的 Where 和 Select 從第一天就是 Lazy 的。Kotlin 的 Collection 版 filter / map 是 Eager，要切成 Sequence 才是 Lazy

Collection 版 vs Sequence 版的根本差異

回顧 day 05 和 day 10，Collection 版的 filter 和 map 長這樣

// Collection 版：直接跑迴圈，立刻算出結果
inline fun <T> Iterable<T>.myFilter(predicate: (T) -> Boolean): List<T> {
    val result = ArrayList<T>()
    for (element in this) {
        if (predicate(element)) result.add(element)
    }
    return result
}

呼叫時會走訪所有元素，並產出新的 List

Sequence 版完全不同。它不跑迴圈，而是回傳一個「包裝 Sequence」。這個包裝物件記住了原本的 Sequence 和 predicate，等到有人呼叫終端操作的時候才真正動手

這個「包裝 + 等到 demand 才執行」的模式叫 pull-based(拉取型)。下游呼叫 iterator().next() 拉一個元素，上游才執行一次

另一類 API 由上游發送資料，例如 RxJava 的 Observable。Kotlin Coroutine 的 Flow 則透過 suspending emit / collect 表達非同步資料流，消費速度與緩衝行為還會受到 buffer、conflate 等運算子影響，不能只用「主動推送」概括

兩個模式各有適用場景

• pull-based(Sequence、IEnumerable)：同步、延遲計算，由消費端逐一 next() 決定拉取速度。集合操作的天然選擇。Java Stream 一樣是延遲求值，但走的是 internal iteration，元素由終端操作往下推送，不是消費端拉
• 非同步串流(RxJava、Flow)：用在網路、UI、感測器等事件流，並明確處理取消、緩衝與消費速度

day 27-31 的 Sequence 是同步 pull-based API。需要處理非同步資料流時，才改用 Flow；兩者的執行模型不同

TDD 實作 Sequence 版 myFilter

Red：先寫測試

@Test
fun `filter even numbers`() {
    val seq = sequenceOf(1, 2, 3, 4, 5).myFilter { it % 2 == 0 }
    assertEquals(listOf(2, 4), seq.toList())
}

@Test
fun `filter is lazy`() {
    var count = 0
    val seq = sequenceOf(1, 2, 3, 4, 5).myFilter { count++; it > 3 }
    assertEquals(0, count)  // 還沒執行
    val first = seq.first()
    assertEquals(4, first)
    assertEquals(4, count)  // 檢查了 1, 2, 3, 4 就找到了
}

@Test
fun `filter on empty sequence yields empty`() {
    val seq = emptySequence<Int>().myFilter { it % 2 == 0 }
    assertEquals(emptyList(), seq.toList())
}

@Test
fun `filter with no match yields empty`() {
    val seq = sequenceOf(1, 3, 5).myFilter { it % 2 == 0 }
    assertEquals(emptyList(), seq.toList())
}

@Test
fun `next throws when exhausted`() {
    val iterator = sequenceOf(1, 3, 5).myFilter { it % 2 == 0 }.iterator()
    assertFalse(iterator.hasNext())
    assertThrows<NoSuchElementException> { iterator.next() }
}

第二個測試是重點。myFilter 之後 count 還是 0，表示 Lambda 完全沒被呼叫。到 first() 才開始走，而且只走到找到第一個符合條件的元素就停了

後面三個測試補上邊界與例外行為。空 Sequence 過濾出來還是空的，沒有任何元素通過 predicate 時結果也是空的，而當 source 走完、沒有下一個元素時呼叫 next()，會丟出 NoSuchElementException。這跟 stdlib 的 Iterator 約定一致，呼叫端應該先用 hasNext() 確認再拿

Green：最小實作

class MyFilteringSequence<T>(
    private val source: Sequence<T>,
    private val predicate: (T) -> Boolean
) : Sequence<T> {
    override fun iterator(): Iterator<T> = object : Iterator<T> {
        val sourceIterator = source.iterator()
        var nextItem: T? = null
        var hasNextItem = false

        override fun hasNext(): Boolean {
            if (hasNextItem) {
                return true
            }
            while (sourceIterator.hasNext()) {
                val item = sourceIterator.next()
                if (predicate(item)) {
                    nextItem = item
                    hasNextItem = true
                    return true
                }
            }
            return false
        }

        override fun next(): T {
            if (!hasNext()) {
                throw NoSuchElementException()
            }
            hasNextItem = false
            @Suppress("UNCHECKED_CAST")
            return nextItem as T
        }
    }
}

fun <T> Sequence<T>.myFilter(predicate: (T) -> Boolean): Sequence<T> {
    return MyFilteringSequence(this, predicate)
}

跟 Collection 版差很多。Collection 版是一個 for 迴圈跑完就結束，Sequence 版是建一個新的 class

MyFilteringSequence 持有原始 Sequence(source) 與過濾條件(predicate)，篩選邏輯放在 iterator() 回傳的匿名 Iterator 裡

hasNext() 的邏輯：如果已經有預存的下一個元素就直接回傳 true。沒有的話，用 while 從 source 拉元素，碰到通過 predicate 的就存起來回傳 true。source 走完都沒找到，回傳 false

next() 的邏輯：先確認 hasNext()，然後把預存的元素回傳，清掉 flag

@Suppress("UNCHECKED_CAST") 是因為 nextItem 宣告為 T?，但 compiler 無法從另一個布林欄位 hasNextItem 推導此處已有合法的下一個值，因此 T? 轉成 T 會產生 unchecked cast 警告。泛型型別抹除也讓執行期無法完整檢查 T。這份實作靠兩個欄位共同維護狀態；如果 T 本身可為 null，nextItem 的 null 也可能是合法元素

Refactor：往 stdlib 的寫法靠近

這個版本已經是 stdlib FilteringSequence 的形狀：一樣靠預存 nextItem 加 flag，在 hasNext() 裡迴圈找下一個通過 predicate 的元素，沒有要再改的地方。stdlib 多出的一個 sendWhen 參數，留到後面的「與 stdlib 原始碼比較」再看

為什麼不用 inline？

Collection 版的 filter 和 map 都是 inline 的(day 04 講過)，編譯器可以把 Lambda 本體展開到呼叫處

Sequence 版不行。原因在於 predicate 需要被存進 MyFilteringSequence 的屬性裡面。Lambda 被存進物件屬性 = Lambda 必須是一個物件 = 無法 inline

技術上，你可以把 myFilter 標成 inline，但 predicate 得標 noinline，因為它會被傳給 MyFilteringSequence 的建構子。如此一來 predicate 仍需要可保存的執行期表示，inline 無法消除這項成本

回顧 day 04 的概念：inline 適合「Lambda 在函式裡面直接執行」的情境。Sequence 版的 Lambda 不是直接執行，而是被存起來延後執行，所以 inline 幫不上忙。等一下實作的 myMap 也是同樣道理，transform 一樣得存進物件屬性

TDD 實作 Sequence 版 myMap

Red：先寫測試

@Test
fun `map doubles`() {
    val seq = sequenceOf(1, 2, 3).myMap { it * 2 }
    assertEquals(listOf(2, 4, 6), seq.toList())
}

@Test
fun `map is lazy`() {
    var count = 0
    val seq = sequenceOf(1, 2, 3).myMap { count++; it * 10 }
    assertEquals(0, count)
    seq.first()
    assertEquals(1, count)  // 只 map 了一個
}

@Test
fun `map on empty sequence yields empty`() {
    val seq = emptySequence<Int>().myMap { it * 2 }
    assertEquals(emptyList(), seq.toList())
}

myMap 的 hasNext() 和 next() 都直接轉給 source，所以它的例外行為跟著 source 走，不另外丟。空 Sequence 進來，map 出去還是空的

Green：最小實作

class MyTransformingSequence<T, R>(
    private val source: Sequence<T>,
    private val transform: (T) -> R
) : Sequence<R> {
    override fun iterator(): Iterator<R> = object : Iterator<R> {
        val sourceIterator = source.iterator()

        override fun hasNext(): Boolean = sourceIterator.hasNext()

        override fun next(): R = transform(sourceIterator.next())
    }
}

fun <T, R> Sequence<T>.myMap(transform: (T) -> R): Sequence<R> {
    return MyTransformingSequence(this, transform)
}

map 比 filter 簡單很多。因為 map 是一對一轉換，source 有多少元素結果就有多少，不需要跳過任何元素。hasNext() 直接問 source，next() 從 source 拿元素然後 transform

Refactor：往 stdlib 的寫法靠近

這個寫法跟 stdlib 的 TransformingSequence 已經一致，hasNext() 和 next() 都直接委派給 source，沒有狀態要管，差異只剩命名，後面的「與 stdlib 原始碼比較」會再對一次

驗證 Lazy 行為

把 filter 和 map 串在一起，用計數器追蹤

@Test
fun `filter and map are lazy together`() {
    var filterCount = 0
    var mapCount = 0
    val result = sequenceOf(1, 2, 3, 4, 5)
        .myFilter { filterCount++; it > 2 }
        .myMap { mapCount++; it * 10 }

    assertEquals(0, filterCount)
    assertEquals(0, mapCount)

    val first = result.first()
    assertEquals(30, first)
    assertEquals(3, filterCount)  // 檢查了 1, 2, 3
    assertEquals(1, mapCount)     // 只 map 了一個
}

這條鏈組起來之後是三層包裝，拉取的方向是由外往內

first()  →  MyTransformingSequence  →  MyFilteringSequence  →  sequenceOf(1..5)
  (要一個值)      (map 那層)                (filter 那層)            (source)

呼叫 first() 之後，每一步發生什麼事、兩個計數器各自變成多少，列成下面這張表

表格裡有幾個地方要注意

步驟 0：myFilter 和 myMap 只是把 source 和 Lambda 塞進物件屬性，兩個計數器都還是 0。這對應測試裡 first() 之前的那兩行 assertEquals(0, ...)

步驟 3 到 5：predicate 被呼叫了三次，因為 filter 的 hasNext() 要一直往 source 拉，拉到第一個通過的元素為止。filterCount 是 3 就是這樣來的

步驟 7：filter 的 next() 內部會再呼叫一次 hasNext()，但這次 hasNextItem 已經是 true，直接回傳，不會再去拉 source。這就是前面用 nextItem 加 flag 預存元素的用意，hasNext() 呼叫幾次結果都一樣，也不會多消耗 source 的元素

步驟 8：transform 只跑了一次，因為只有一個元素真的走到 map 那層。mapCount 是 1

整趟走完，元素 4 和 5 從頭到尾沒被 source 吐出來過，predicate 和 transform 都沒碰過它們。這就是 Lazy 的好處。換成 Collection 版，filter 會先把 1 到 5 全部檢查完產生 [3, 4, 5]，map 再把三個元素全部乘 10 產生 [30, 40, 50]，最後只取第一個，前面多算的都白算了

從 List 出發

上面的測試都用 sequenceOf 建 source，但實際寫程式的時候，手上通常是一個 List。這時要用 day 28 做好的 myAsSequence() 當入口

@Test
fun `list as sequence keeps the chain lazy`() {
    var filterCount = 0
    var mapCount = 0
    val list = listOf(1, 2, 3, 4, 5)
    val result = list.myAsSequence()
        .myFilter { filterCount++; it > 2 }
        .myMap { mapCount++; it * 10 }

    assertEquals(0, filterCount)
    assertEquals(0, mapCount)

    assertEquals(30, result.first())
    assertEquals(3, filterCount)
    assertEquals(1, mapCount)
}

兩個計數器的結果跟 sequenceOf 那個版本一模一樣，3 和 1。換掉入口不影響後面的行為

原因在 myAsSequence() 的實作本身

fun <T> Iterable<T>.myAsSequence(): Sequence<T> {
    return Sequence { this.iterator() }
}

它沒有複製 List，也沒有先走過任何元素，只是把「要 iterator 的時候跟這個 List 要」包成一個 Sequence。所以拉取鏈只是從三層變四層，最裡面多接一個 List 的 iterator

first()  →  MyTransformingSequence  →  MyFilteringSequence  →  myAsSequence 的 Sequence  →  listOf(1..5)

也因為沒有複製，4 和 5 這兩個元素雖然一直待在 List 裡面，但 predicate 和 transform 都不會碰到它們

要對照的話，同一個 List 走 Collection 版是這樣

@Test
fun `collection version walks every element`() {
    var filterCount = 0
    var mapCount = 0
    val list = listOf(1, 2, 3, 4, 5)
    val first = list
        .myFilter { filterCount++; it > 2 }   // day 05 的 Collection 版
        .myMap { mapCount++; it * 10 }        // day 10 的 Collection 版
        .first()

    assertEquals(30, first)
    assertEquals(5, filterCount)  // 五個元素全部檢查過
    assertEquals(3, mapCount)     // 三個元素全部轉換過
}

兩個測試拿到的答案都是 30，同一份資料、同樣的 Lambda，差別只在中間有沒有 myAsSequence()。Collection 版是 5 和 3，Sequence 版是 3 和 1

這兩段程式碼能並存，是因為 myFilter 有兩個接收者不同的版本：day 05 那個掛在 Iterable<T> 上，這篇這個掛在 Sequence<T> 上。List 是 Iterable 不是 Sequence，所以 list.myFilter { } 會選到 Collection 版，中間加了 myAsSequence() 才會換成 Sequence 版。stdlib 的 filter 也是同樣的安排

與 stdlib 原始碼比較

原始碼位置：kotlin.sequences 的 Sequences.kt

stdlib 的 FilteringSequence 跟我們幾乎一樣

internal class FilteringSequence<T>(
    private val sequence: Sequence<T>,
    private val sendWhen: Boolean = true,
    private val predicate: (T) -> Boolean
) : Sequence<T> { ... }

多了一個 sendWhen 參數。當 sendWhen = true 就是 filter，sendWhen = false 就是 filterNot。用同一個 class 處理兩種情況

stdlib 的 TransformingSequence 也跟我們一樣，差異只在命名風格

小結

Sequence 的 filter 和 map 不是跑迴圈產出結果，而是建立一層包裝

MyFilteringSequence 包住原始 Sequence 加上 predicate，MyTransformingSequence 包住原始 Sequence 加上 transform。一層套一層，等到終端操作出現才從最外層往裡面拉元素

下一篇把中間操作和終端操作整理清楚，再手刻 Sequence 版的 take、first、toList

參考資料

• Kotlin 官方文件：Sequences
• Kotlin 官方文件：Inline functions
• Kotlin API：Sequence.filter
• Kotlin API：Sequence.map
• Kotlin API：Sequence
• Kotlin API：Iterator
• Kotlin stdlib 原始碼：_Sequences.kt
• .NET API：Enumerable.Where
• .NET API：Enumerable.Select
• C# 官方文件：延遲執行與 Lazy Evaluation

同步刊登於 Blog

圖片來源：AI 產生